package com.zk.algorithm.array;

import com.zk.algorithm.Utils;
import com.zk.algorithm.annotation.JianZhiOffer;

import java.util.LinkedList;
import java.util.List;

/**
 * 圆圈中最后剩下的数字: 0, 1, ..., n -1 这 n 个数字排成一个圆圈，从数字 0 开始每次从这个圆圈里删除第 m 个数字。
 * 求出最后剩下的这个数字
 *
 * 0, 1, 2, 3, 4
 * ↑     ↑(D)
 * ----------------------
 * 0, 1, 3, 4
 *       ↑
 * ↑(D)
 * ----------------------
 * 1, 3, 4
 * ↑     ↑(D)
 * ----------------------
 * 1, 3
 * ↑
 * ↑(D)
 * ----------------------
 *
 * 这题是著名的约瑟夫环问题:
 *    - 环形链表模拟
 *    - 根据规律直接计算
 *
 * @author zk
 */
@JianZhiOffer("45")
public class LastRemainderOfTheCircle {

    public int lastRemaining(int n, int m) {
        if (n < 1 || m < 1) {
            return -1;
        }

        List<Integer> list = new LinkedList<>();
        for (int i = 0; i <= n; i++) {
            list.add(i);
        }

        // 要删除元素的位置
        int idx = 0;

        while (list.size() > 1) {

            // 只要移动m-1次就可以移动到下一个要删除的元素上
            for (int i = 1; i < m; i++) {
                idx = (idx + 1) % list.size(); // 【A】
            }

            list.remove(idx);
        }

        return list.get(0);
    }

    public static void main(String... args) {
        Utils.println(new LastRemainderOfTheCircle().lastRemaining(4, 3));
    }

}
